package 二叉树;

import javax.swing.tree.TreeNode;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
public class Solution98 {
    public static void main(String[] args) {
        Node left = new Node(null, null, 4);
        Node right = new Node(null, null, 3);
        Node node = new Node(left, right, 2);
        boolean b = isValidBST(node);
        System.out.println(b);

    }

    /**
     * 判断是否是二叉搜索树
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     *
     * @param root
     * @return
     */
    public static boolean isValidBST(Node root) {
        //base
        if (root == null) {
            return true;
        }
        boolean le = true;

        boolean l = isValidBST(root.left);
        if (root.left != null) {
            le = root.left.value < root.value;
        }
        boolean ri = true;

        if (root.right != null) {
            ri = root.right.value > root.value;
        }
        boolean r = isValidBST(root.right);
        return l && r && le && ri;
    }

}
